package com.xcf.weekly_2020_200;

import java.util.LinkedList;
import java.util.List;

public class SwapGrid {

    /**
     * 1. 统计尾部每行0的连续个数
     * 2. 移动换行
     * 第一行 n-1 个 0
     * 第二行 n-2 个 0
     * ....
     * 第n行 0 个 0
     */
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        List<Integer> countList = new LinkedList<>( );
        for (int i = 0; i < n; i++) {
            int zeroNum = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    zeroNum++;
                } else {
                    break;
                }
            }
            countList.add(zeroNum);
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            int zeroLimit = n - i - 1;
            if (countList.get(i) >= zeroLimit) {
                continue;
            }
            int j = i;
            for (; j < n; j++) {
                if (countList.get(j) >= zeroLimit) {
                    Integer temp = countList.remove(j);
                    countList.add(i, temp);
                    result = result + j - i;
                    break;
                }
            }
            if (j >= n) {
                return -1;
            }
        }
        return result;
    }


    public static void main(String[] args) {
        SwapGrid swapGrid = new SwapGrid( );
        int result = swapGrid.minSwaps(new int[][]{{0, 0, 1}, {1, 1, 0}, {1, 0, 0}});
        System.out.println("result = " + result);
        result = swapGrid.minSwaps(new int[][]{{0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}});
        System.out.println("result = " + result);
        result = swapGrid.minSwaps(new int[][]{{1, 0, 0}, {1, 1, 0}, {1, 1, 1}});
        System.out.println("result = " + result);
    }
}
